package Hot100.Medium.HeapAndStack;

import java.util.HashMap;
import java.util.PriorityQueue;

public class LC347_TopKFrequent {
    public int[] topKFrequent(int[] nums, int k){

        //用Map记录数组中各个数字出现的次数
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int n : nums){
            map.put(n, map.getOrDefault(n, 0) + 1);
        }
        //初始化小顶堆,也就是优先队列，通过Lambda表达式指定生序排序
        //存储二元组（num，cnt）cnt表示元素num在数组中出现的次数
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> map.get(a) - map.get(b));
        for(Integer key : map.keySet()){
            if(queue.size() < k){//小顶堆元素个数小于k个，直接加入
                queue.add(key);
            } else {
                //如果当前元素出现次数比小顶堆顶还大，直接弹出堆顶，因为其出现次数最少
                if(map.get(key) > map.get(queue.peek())){
                    queue.poll();
                    queue.add(key);
                }
            }
        }
        //此时可知queue中存放的是这些元素，遍历输出即可
        int[] res = new int[k];
        int i = k - 1;
        while (!queue.isEmpty()){
            res[i--] = queue.poll();
        }
        return res;
    }
}
